/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.MergeableHeap
import org.junit.Assert
import org.junit.Assert.assertEquals
import org.junit.BeforeClass
import org.junit.Test
import java.io.*
import java.util.*
import kotlin.math.ceil

class BinaryTreeSoftAddressableHeapTest {
    @Test
    fun testNoCorruptionAsHeap() {
        val n = SIZE
        val epsilon = 1.0 / (n + 1)

        val a = BinaryTreeSoftAddressableHeap<Int, String>(epsilon)

        for (i in 0 until n) {
            a.insert(i)
        }

        for (i in 0 until n) {
            Assert.assertEquals(i.toLong(), a.deleteMin().key.toLong())
        }

        Assert.assertTrue(a.isEmpty)
    }

    @Test
    fun testNoCorruptionWithComparatorAsHeap() {
        val n = SIZE
        val epsilon = 1.0 / (n + 1)

        val a = BinaryTreeSoftAddressableHeap<Int, String>(
            epsilon,
            comparator
        )

        for (i in 0 until n) {
            a.insert(i)
        }

        for (i in SIZE - 1 downTo 0) {
            Assert.assertEquals(i.toLong(), a.deleteMin().key.toLong())
        }

        Assert.assertTrue(a.isEmpty)
    }

    @Test
    fun testSort1RandomSeed1() {
        val h: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(1.0 / (SIZE + 1))

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSort1RandomSeed1WithComparator() {
        val h: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(
            1.0 / (SIZE + 1),
            comparator
        )

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) >= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testComparator() {
        val h: AddressableHeap<Long, Void> = BinaryTreeSoftAddressableHeap(0.5)

        Assert.assertNull(h.comparator())
    }

    @Test
    fun testFindMinDeleteMinSameObject() {
        val h: AddressableHeap<Long, String> = BinaryTreeSoftAddressableHeap(0.5)

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        while (!h.isEmpty) {
            Assert.assertEquals(h.findMin(), h.deleteMin())
        }
    }

    @Test
    fun testSoftHeap0() {
        testSoftHeapInsert(0.01, null)
        testSoftHeapInsert(0.01, comparator)
        testSoftHeapInsertDeleteMin(0.01, null)
        testSoftHeapInsertDeleteMin(0.01, comparator)
        testSoftHeapInsertDelete(0.01, null)
        testSoftHeapInsertDelete(0.01, comparator)
        testSoftHeapInsertDeleteDeleteMin(0.01, null)
        testSoftHeapInsertDeleteDeleteMin(0.01, comparator)
    }

    @Test
    fun testSoftHeap1() {
        testSoftHeapInsert(0.25, null)
        testSoftHeapInsert(0.25, comparator)
        testSoftHeapInsertDeleteMin(0.25, null)
        testSoftHeapInsertDeleteMin(0.25, comparator)
        testSoftHeapInsertDelete(0.25, null)
        testSoftHeapInsertDelete(0.25, comparator)
        testSoftHeapInsertDeleteDeleteMin(0.25, null)
        testSoftHeapInsertDeleteDeleteMin(0.25, comparator)
    }

    @Test
    fun testSoftHeap2() {
        testSoftHeapInsert(0.5, null)
        testSoftHeapInsert(0.5, comparator)
        testSoftHeapInsertDeleteMin(0.5, null)
        testSoftHeapInsertDeleteMin(0.5, comparator)
        testSoftHeapInsertDelete(0.5, null)
        testSoftHeapInsertDelete(0.5, comparator)
        testSoftHeapInsertDeleteDeleteMin(0.5, null)
        testSoftHeapInsertDeleteDeleteMin(0.5, comparator)
    }

    @Test
    fun testSoftHeap3() {
        testSoftHeapInsert(0.75, null)
        testSoftHeapInsert(0.75, comparator)
        testSoftHeapInsertDeleteMin(0.75, null)
        testSoftHeapInsertDeleteMin(0.75, comparator)
        testSoftHeapInsertDelete(0.75, null)
        testSoftHeapInsertDelete(0.75, comparator)
        testSoftHeapInsertDeleteDeleteMin(0.75, null)
        testSoftHeapInsertDeleteDeleteMin(0.75, comparator)
    }

    @Test
    fun testSoftHeap4() {
        testSoftHeapInsert(0.99, null)
        testSoftHeapInsert(0.99, comparator)
        testSoftHeapInsertDeleteMin(0.99, null)
        testSoftHeapInsertDeleteMin(0.99, comparator)
        testSoftHeapInsertDelete(0.99, null)
        testSoftHeapInsertDelete(0.99, comparator)
        testSoftHeapInsertDeleteDeleteMin(0.99, null)
        testSoftHeapInsertDeleteDeleteMin(0.99, comparator)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction1() {
        BinaryTreeSoftAddressableHeap<Int, Void>(0.0)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction2() {
        BinaryTreeSoftAddressableHeap<Int, Void>(1.0)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction3() {
        BinaryTreeSoftAddressableHeap<Int, Void>(-1.0)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction4() {
        BinaryTreeSoftAddressableHeap<Int, Void>(2.0)
    }

    @Test(expected = NoSuchElementException::class)
    fun testIllegalDeleteMin() {
        BinaryTreeSoftAddressableHeap<Int, Void>(0.5).deleteMin()
    }

    @Test(expected = NoSuchElementException::class)
    fun testIllegalFindMin() {
        BinaryTreeSoftAddressableHeap<Int, Void>(0.5).findMin()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalDeleteTwice() {
        val h = BinaryTreeSoftAddressableHeap<Int, Void>(0.5)
        val e: AddressableHeap.Handle<Int, Void> = h.insert(1)
        e.delete()
        e.delete()
    }

    @Test
    fun testGetValue() {
        val h: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(0.5)
        val e = h.insert(1, "999")
        assertEquals("999", e.value)
    }

    @Test(expected = UnsupportedOperationException::class)
    fun testNoDecreaseKey() {
        val h: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(0.5)
        val e = h.insert(1, "999")
        e.decreaseKey(0)
    }

    @Test
    fun testIsEmpty() {
        val h: AddressableHeap<Int, Void> = BinaryTreeSoftAddressableHeap(0.5)
        Assert.assertTrue(h.isEmpty)
        h.insert(1)
        Assert.assertFalse(h.isEmpty)
    }

    @Test
    fun testClear() {
        val h: AddressableHeap<Int, Void> = BinaryTreeSoftAddressableHeap(0.5)
        Assert.assertTrue(h.isEmpty)
        h.insert(1)
        h.insert(2)
        h.insert(3)
        h.insert(4)
        Assert.assertFalse(h.isEmpty)
        Assert.assertEquals(4, h.size())
        h.clear()
        Assert.assertTrue(h.isEmpty)
        Assert.assertEquals(0, h.size())
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h: AddressableHeap<Long, Void?> = BinaryTreeSoftAddressableHeap(1.0 / 16)

        for (i in 0..14L) {
            h.insert(i)
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as AddressableHeap<Long, Void?>

        for (i in 0..14L) {
            Assert.assertEquals((15 - i), h.size())
            assertEquals(i, h.findMin().key)
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testMeldGeneric() {
        val h1: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(1.0 / (SIZE + 1))

        if (h1 is MergeableHeap<*>) {
            for (i in 0 until SIZE) {
                h1.insert(2 * i)
            }

            val h2: AddressableHeap<Int, String> = BinaryTreeSoftAddressableHeap(1.0 / (SIZE + 1))
            for (i in 0 until SIZE) {
                h2.insert(2 * i + 1)
            }

            (h1 as MergeableHeap<Int>).meld((h2 as MergeableHeap<Int>))

            Assert.assertEquals(h1.size(), (SIZE * 2).toLong())
            Assert.assertEquals(h2.size(), 0)

            var prev: Int? = null
            var cur: Int
            while (!h1.isEmpty) {
                cur = (h1 as AddressableHeap).findMin().key
                (h1 as AddressableHeap).deleteMin()
                if (prev != null) {
                    Assert.assertTrue(prev.compareTo(cur) <= 0)
                }
                prev = cur
            }
        }
    }

    @Test
    fun testMeld1() {
        testSoftHeapMeld(SIZE, 0.10, null)
        testSoftHeapMeld(SIZE, 0.10, comparator)
        testSoftHeapMeld(SIZE, 0.25, null)
        testSoftHeapMeld(SIZE, 0.25, comparator)
        testSoftHeapMeld(SIZE, 0.5, null)
        testSoftHeapMeld(SIZE, 0.5, comparator)
        testSoftHeapMeld(SIZE, 0.75, null)
        testSoftHeapMeld(SIZE, 0.75, comparator)
        testSoftHeapMeld(SIZE, 0.95, null)
        testSoftHeapMeld(SIZE, 0.95, comparator)
    }

    @Test
    fun testMeld2() {
        testSoftHeapMeldSmallLarge(SIZE, 0.10, null)
        testSoftHeapMeldSmallLarge(SIZE, 0.10, comparator)
        testSoftHeapMeldSmallLarge(SIZE, 0.25, null)
        testSoftHeapMeldSmallLarge(SIZE, 0.25, comparator)
        testSoftHeapMeldSmallLarge(SIZE, 0.5, null)
        testSoftHeapMeldSmallLarge(SIZE, 0.5, comparator)
        testSoftHeapMeldSmallLarge(SIZE, 0.75, null)
        testSoftHeapMeldSmallLarge(SIZE, 0.75, comparator)
        testSoftHeapMeldSmallLarge(SIZE, 0.95, null)
        testSoftHeapMeldSmallLarge(SIZE, 0.95, comparator)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMeldWrong1() {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(
            0.5,
            comparator
        )
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(0.5)

        h1.meld(h2)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMeldWrong2() {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(0.4)
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(0.7)

        h1.meld(h2)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMeldWrong3() {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(0.4)
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(
            0.4,
            comparator
        )

        h1.meld(h2)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMeldWrong4() {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(
            0.4,
            comparator
        )
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(
            0.4
        ) { o1, o2 -> comparator!!.compare(o1, o2) }

        h1.meld(h2)
    }

    @Test(expected = IllegalStateException::class)
    fun testMultipleMelds() {
        val a = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        val c = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        c.insert(18)
        c.insert(19)
        c.insert(20)
        c.insert(21)

        a.meld(b)
        a.meld(b)
        validateSoftHeap(a, 0.5, 12L)
    }

    @Test
    fun testDeleteAfterMultipleMelds() {
        val a = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        b.insert(14)
        b.insert(15)
        val b3: AddressableHeap.Handle<Int, String> = b.insert(16)
        b.insert(17)

        val c = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        c.insert(18)
        c.insert(19)
        val c3: AddressableHeap.Handle<Int, String> = c.insert(20)
        c.insert(21)

        a.meld(b)
        a.meld(c)
        validateSoftHeap(a, 0.5, 12L)
        b3.delete()
        validateSoftHeap(a, 0.5, 12L)
        c3.delete()
        validateSoftHeap(a, 0.5, 12L)
    }

    @Test(expected = IllegalStateException::class)
    fun testInsertAfterAMeld() {
        val a = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        a.meld(b)
        b.insert(30)
    }

    @Test
    fun testCascadingMelds() {
        val a = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        a.insert(10)
        a.insert(11)
        a.insert(12)
        a.insert(13)

        val b = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        b.insert(14)
        b.insert(15)
        b.insert(16)
        b.insert(17)

        val c = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        c.insert(18)
        c.insert(19)
        c.insert(20)
        c.insert(21)

        val d = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        d.insert(22)
        d.insert(23)
        d.insert(24)
        d.insert(25)

        val e = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        e.insert(26)
        e.insert(27)
        e.insert(28)
        e.insert(29)

        d.meld(e)
        c.meld(d)
        b.meld(c)
        a.meld(b)

        Assert.assertEquals(20, a.size())
        Assert.assertEquals(0, b.size())
        Assert.assertEquals(0, c.size())
        Assert.assertEquals(0, d.size())
        Assert.assertEquals(0, e.size())

        validateSoftHeap(a, 0.5, 20L)
    }

    @Test
    fun testDeleteAfterCascadingMelds() {
        val a = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        a.insert(10)
        a.insert(11)
        val a3: AddressableHeap.Handle<Int, String> = a.insert(12)
        a.insert(13)

        val b = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        b.insert(14)
        b.insert(15)
        val b3: AddressableHeap.Handle<Int, String> = b.insert(16)
        b.insert(17)

        val c = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        c.insert(18)
        c.insert(19)
        val c3: AddressableHeap.Handle<Int, String> = c.insert(20)
        c.insert(21)

        val d = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        d.insert(22)
        d.insert(23)
        val d3: AddressableHeap.Handle<Int, String> = d.insert(24)
        d.insert(25)

        val e = BinaryTreeSoftAddressableHeap<Int, String>(0.5)
        e.insert(26)
        e.insert(27)
        val e3: AddressableHeap.Handle<Int, String> = e.insert(28)
        e.insert(29)

        d.meld(e)
        c.meld(d)
        b.meld(c)
        a.meld(b)

        Assert.assertEquals(20, a.size())
        Assert.assertEquals(0, b.size())
        Assert.assertEquals(0, c.size())
        Assert.assertEquals(0, d.size())
        Assert.assertEquals(0, e.size())

        e3.delete()
        validateSoftHeap(a, 0.5, 20L)
        d3.delete()
        validateSoftHeap(a, 0.5, 20L)
        c3.delete()
        validateSoftHeap(a, 0.5, 20L)
        b3.delete()
        validateSoftHeap(a, 0.5, 20L)
        a3.delete()
        validateSoftHeap(a, 0.5, 20L)
    }

    @Test(expected = NullPointerException::class)
    fun testInsertNullKey() {
        BinaryTreeSoftAddressableHeap<Int?, String>(0.5).insert(null)
    }

    private fun testSoftHeapMeld(n: Int, epsilon: Double, comparator: Comparator<Int?>?) {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        for (i in 0 until n) {
            if (i % 2 == 0) {
                h1.insert(i)
            } else {
                h2.insert(i)
            }
        }

        validateSoftHeap(h1, epsilon, (n / 2).toLong())
        Assert.assertEquals((n / 2).toLong(), h1.size())
        validateSoftHeap(h2, epsilon, (n / 2).toLong())
        Assert.assertEquals((n / 2).toLong(), h2.size())

        h1.meld(h2)

        validateSoftHeap(h1, epsilon, n.toLong())
        validateSoftHeap(h2, epsilon, n.toLong())
    }

    private fun testSoftHeapMeldSmallLarge(n: Int, epsilon: Double, comparator: Comparator<Int?>?) {
        val h1 = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )
        val h2 = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        for (i in 0 until n / 3) {
            h1.insert(i)
        }

        for (i in n / 3 until n) {
            h2.insert(i)
        }

        validateSoftHeap(h1, epsilon, (n / 3).toLong())
        Assert.assertEquals((n / 3).toLong(), h1.size())
        validateSoftHeap(h2, epsilon, (2 * n / 3).toLong())
        Assert.assertEquals(ceil(2.0 * n / 3.0).toInt().toLong(), h2.size())

        h1.meld(h2)

        validateSoftHeap(h1, epsilon, n.toLong())
        validateSoftHeap(h2, epsilon, n.toLong())
    }

    private fun testSoftHeapInsert(epsilon: Double, comparator: Comparator<Int?>?) {
        val n = SIZE

        val a = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        for (i in 0 until n) {
            a.insert(i)
        }

        validateSoftHeap(a, epsilon, n.toLong())
    }

    private fun testSoftHeapInsertDeleteMin(epsilon: Double, comparator: Comparator<Int?>?) {
        val n = SIZE

        val a = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        for (i in 0 until n) {
            a.insert(i)
        }

        for (i in 0 until n / 4) {
            a.deleteMin()
        }

        validateSoftHeap(a, epsilon, n.toLong())
    }

    private fun testSoftHeapInsertDelete(epsilon: Double, comparator: Comparator<Int?>?) {
        val n = SIZE

        val h = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(n){  h.insert(it) }
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(n)
        for (i in 0 until n) {
            array[i] = h.insert(i)
        }*/

        for (i in 0 until n / 4) {
            array[i].delete()
        }

        validateSoftHeap(h, epsilon, n.toLong())
    }

    private fun testSoftHeapInsertDeleteDeleteMin(epsilon: Double, comparator: Comparator<Int?>?) {
        val n = SIZE

        val h = BinaryTreeSoftAddressableHeap<Int, Void>(
            epsilon,
            comparator
        )

        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(n){i-> h.insert(i)}
        /*array = arrayOfNulls<AddressableHeap.Handle<*, *>>(n)
        for (i in 0 until n) {
            array[i] = h.insert(i)
        }*/

        for (i in 0 until n / 4) {
            h.deleteMin()
        }

        for (i in n - 1 downTo 3 * n / 4) {
            try {
                array[i].delete()
            } catch (e: IllegalArgumentException) {
                // ignore, already deleted due to corruption
            }
        }

        validateSoftHeap(h, epsilon, n.toLong())
    }

    private class KeyCount(var total: Long, var corrupted: Long)

    companion object {
        private const val SIZE = 100000

        private var comparator: Comparator<Int?>? = null

        @JvmStatic
        @BeforeClass
        fun setUpClass(): Unit {
            comparator = Comparator { o1, o2 ->
                if (o1!! < o2!!) {
                    1
                } else if (o1 > o2) {
                    -1
                } else {
                    0
                }
            }
        }

        /**
         * Validate the invariants of a soft heap.
         *
         * @param h
         * the soft heap
         * @param epsilon
         * the error rate of the soft heap
         * @param totalInsertedElements
         * the total number of elements added in the heap
         */
        private fun <K, V> validateSoftHeap(
            h: BinaryTreeSoftAddressableHeap<K, V>, epsilon: Double,
            totalInsertedElements: Long
        ) {
            var total: Long = 0
            var corrupted: Long = 0
            val comparator = h.comparator()
            var cur  = h.rootList.head
            while (cur != null) {
                // validate each heap
                val kc = validateRoot(cur.root, comparator)
                // keep total count of total and corrupted elements
                total += kc.total
                corrupted += kc.corrupted
                cur = cur.next
            }
            Assert.assertEquals(total, h.size())
            Assert.assertTrue("Too many corrupted elemenets", corrupted <= totalInsertedElements * epsilon)

            // validate suffix min pointers
            var minSoFar: K? = null
            cur = h.rootList.tail
            while (cur != null) {
                // find min by hand
                if (minSoFar == null) {
                    minSoFar = cur.root.cKey
                } else {
                    if (comparator == null) {
                        if ((cur.root.cKey as Comparable<K>).compareTo(minSoFar) <= 0) {
                            minSoFar = cur.root.cKey
                        }
                    } else {
                        if (comparator.compare(cur.root.cKey, minSoFar) <= 0) {
                            minSoFar = cur.root.cKey
                        }
                    }
                }

                // compare with suffix min
                Assert.assertEquals(minSoFar, cur.suffixMin.root.cKey)

                // keep total count of total and corrupted elements
                cur = cur.prev
            }
        }

        private fun <K, V> validateRoot(
            root: BinaryTreeSoftAddressableHeap<K, V>.TreeNode,
            comparator: Comparator<in K?>?
        ): KeyCount {
            Assert.assertTrue(root.parent != null)
            if (root.left != null) {
                Assert.assertEquals(root.left!!.parent, root)
                Assert.assertTrue(root.rank > root.left!!.rank)
                if (comparator == null) {
                    Assert.assertTrue((root.cKey as Comparable<K>) <= root.left!!.cKey!!)
                } else {
                    Assert.assertTrue(comparator.compare(root.cKey, root.left!!.cKey) <= 0)
                }
            }
            if (root.right != null) {
                Assert.assertEquals(root.right!!.parent, root)
                Assert.assertTrue(root.rank > root.right!!.rank)
                if (comparator == null) {
                    Assert.assertTrue((root.cKey as Comparable<K>) <= root.right!!.cKey!!)
                } else {
                    Assert.assertTrue(comparator.compare(root.cKey, root.right!!.cKey) <= 0)
                }
            }
            if (root.left != null && root.right != null) {
                Assert.assertEquals(root.left!!.rank.toLong(), root.right!!.rank.toLong())
            }
            Assert.assertTrue(root.cKey != null)
            Assert.assertTrue(root.cHead != null)
            Assert.assertTrue(root.cHead!!.tree == root)

            Assert.assertTrue(root.cSize > 0)
            var total: Long = 0
            var corrupted: Long = 0
            var e  = root.cHead
            while (e != null) {
                total++
                if (comparator == null) {
                    if ((e.key as Comparable<K>) < root.cKey!!) {
                        corrupted++
                    }
                } else {
                    if (comparator.compare(e.key, root.cKey) < 0) {
                        corrupted++
                    }
                }
                e = e.next
            }
            /*
         * Due to ghost elements (if delete operation is used)
         */
            Assert.assertTrue(total > 0 && total <= root.cSize)

            if (root.left != null) {
                val leftKeyCount = validateRoot(root.left!!, comparator)
                total += leftKeyCount.total
                corrupted += leftKeyCount.corrupted
            }

            if (root.right != null) {
                val rightKeyCount = validateRoot(root.right!!, comparator)
                total += rightKeyCount.total
                corrupted += rightKeyCount.corrupted
            }
            return KeyCount(total, corrupted)
        }
    }
}
